package LimitedTimeGame.Day_0228;

/**
 * @author zxc
 * @date 2023/02/28 08:07
 **/

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 题目 ：使得数组严格递增
 * 题目详述 :
 * 给你两个整数数组arr1 和 arr2，返回使arr1严格递增所需要的最小「操作」数（可能为 0）。
 * 每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，
 * 分别为i 和j，0 <=i < arr1.length和0 <= j < arr2.length，然后进行赋值运算arr1[i] = arr2[j]。
 * 如果无法让arr1严格递增，请返回-1。
 *
 * 提示：
 * 1 <= arr1.length, arr2.length <= 2000
 * 0 <= arr1[i], arr2[i] <= 10^9
 *
 */
public class MakeArrayIncreasing {
    public static void main(String[] args) {
        System.out.println(makeArrayIncreasing(new int[]{1,5,3,6,7}, new int[]{1,6,3,3}));
    }
    /**
     * 思路 ：
     * 动态规划
     * ===》
     * （1）假设f(i)为替换arr1数组的前i+1个元素 && 同时保证第i个元素(arr1[i])不被替换 所需要的最少操作次数;
     *  即，遍历到arr1的最后一个元素的话，则其也可能被替换，所以选择在原本的arr1数组尾部加上元素m（永远是该arr1数组中的最大值）
     *
     * （2）若是arr1[i-1]不被替换的话，需要满足条件 ：arr1[i-1] < arr1[i]
     *  ===》
     *  f(i) = min( f(i) , f(i-1) );
     *
     * （3）若是arr1[i-1]是要被替换的话，则f(i) = f(i - 2) + 1;
     *  同时，又由于arr1[i-1]也是可以被替换的，当替换了k个数之后，所以 f(i) = min( f(i - k - 1) + k);
     *  ===>
     *  即，连续替换 :
     *  1.首先，对于arr2数组进行排序 && 去重;
     *  2.其次，当要对于arr1[i - 1]进行替换时，则需要在arr2中寻找到第一个大于等于arr1[i]的arr2[j]，
     *  则选择使用arr2[j-1]来对于arr1[i-1]进行替换;
     *  3.以此类推，直至arr1[i - k]被替换为arr2[j - k];
     *
     * （4）若是arr1[i - 1]要被替换的话，则应该满足 arr2[j - k] > arr1[i - k - 1];
     *  ===》
     *  所需要满足的条件为 k <= j && k <= i;
     *  特殊情况 ：f(0)是代表了 替换数组arr1的前1个元素 && 同时保证第0个元素（arr1[0]）不被替换 的最少操作次数;
     *  ===》即，无论如何，第0个元素（arr1[0]）是永远不会被替换的；
     *  所以，需要在原本的arr1[0]元素之前添加一个元素，保证其永远不会被替换,将其作为f(0)存在
     *
     * @param arr1
     * @param arr2
     * @return
     */
    public static int makeArrayIncreasing(int[] arr1, int[] arr2) {
        // 1.对于arr1数组进行预处理;
        // 使用temp数组用来保存 arr1数组中的元素（增加了头结点[-1]和尾节点[Integer.MAX_VALUE]）
        // 即，用来保证arr1数组中所有元素都是可以被获取到的;
        int[] temp1 = new int[arr1.length + 2];
        temp1[0] = -1;
        temp1[arr1.length + 1] = Integer.MAX_VALUE;
        for(int i = 0 ; i < arr1.length ; i++){
            temp1[i + 1] = arr1[i];
        }
        // 2.对于arr2数组进行预处理;
        // 使用HashSet数据结构，实现对于arr2中元素的去重 &&排序;
        HashSet<Integer> hashSet = new HashSet<>();
        for(int i = 0 ; i < arr2.length ; i++){
            hashSet.add(arr2[i]);
        }
        List<Integer> list = hashSet.stream().sorted().collect(Collectors.toList());
        int[] temp2 = new int[list.size()];
        int n = 0;
        while(!list.isEmpty()){
            temp2[n] = list.get(0);
            list.remove(0);
            n++;
        }
        // 3.辅助数组dp，来保存 保证前n+1个元素递增 && 第n个元素不进行替换的最少操作次数;
        final Integer MAX_VALUE = 1000000008;
        int len1 = temp1.length;
        int len2 = temp2.length;
        int[] dp = new int[len1];
        // 辅助数组dp进行初始化时候，需要给其赋予MAX_VALUE;
        Arrays.fill(dp , MAX_VALUE);
        // 即，新加入的首元素-1 是必然不可能需要进行替换掉
        dp[0] = 0;
        // 4.迭代遍历 arr1中所有元素;
        for(int i = 1 ; i < len1 ; i++){
            // （1）选择进行替换操作;
            // 获取 temp2数组中大于等于 temp1[i]的首个元素
            int j = lowerBound(temp2 , 0 , len2 - 1 , temp1[i]);
            // 若是temp2中不存在大于等于该元素的数组元素下标，则需要去将其指向 temp2最后一个元素的后一个虚拟元素;
            if(temp2[j] < temp1[i]){
                j++;
            }
            // 5.选择替换之前的元素，来保证递增;
            // 即，选择替换temp1中元素个数;
            // 所需要满足的条件 ：
            // （1）最后一个替换的元素temp2[j - k] > temp1[i - k - 1]，这样子才能够去保证递增;
            // （2）k（所能够替换元素的个数）<= [ j（temp2数组中可供替换的元素个数）] && [i（temp1数组中允许替换的元素个数，除去首元素和尾元素;）]
            //  temp1数组中，头元素是在temp1数组中最小的元素 && 尾元素是在temp1数组中最大的元素;
            /**
             * 思考 ：
             * 为什么要引入头元素和尾元素？
             * ===》
             * 由于假设为 f(i)为替换arr1数组的前i+1个元素 && 同时保证第i个元素(arr1[i])不被替换 所需要的最少操作次数;
             * 即，为了保证arr1中所有元素都是可替换的，引入头元素（最小元素）和尾元素（最大元素），来保证arr1中所有元素皆可以进行替换;
             *
             */
            for(int k = 1 ; k <= Math.min(i - 1 , j) ; k++){
                if(temp2[j - k] > temp1[i - k - 1]){
                    dp[i] = Math.min(dp[i] , dp[i - k - 1] + k);
                }
            }
            // 6.选择不进行替换操作;
            // （由于temp1[i] && temp1[i-1]本身就是递增的;）
            if(temp1[i - 1] < temp1[i]){
                dp[i] = Math.min(dp[i] , dp[i - 1]);
            }
        }
        // 若是dp[len1 - 1] == MAX_VALUE,就代表了未能够找到 使用arr2中元素去替换arr1中元素，来实现arr1数组递增的方法;
        return dp[len1 - 1] == MAX_VALUE ? -1 : dp[len1 - 1];
    }
    // 实现lowerBound函数 ：获取nums数组中，大于等于target的首个值;
    public static int lowerBound(int[] nums , int left , int right , int target){
        // 二分查找;
        while(left < right){
            int mid = (left + right) / 2;
            if(nums[mid] >= target){
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }
        return left;
    }
    // 实现lowerBound2函数 ：获取nums数组中，大于target的首个值;
    public int lowerBound2(int[] nums , int left , int right , int target){
        // 二分查找;
        while(left < right){
            int mid = (left + right) / 2;
            if(nums[mid] <= target){
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        return left;
    }
}
